<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
    <script>
      let arr = [2, 9, 6, 7, 4, 3, 1, 7]
      // 冒泡排序
      // 1.比较相邻的元素，前者比后者大的话，两者交换位置。
      // 2.对每一对相邻元素做相同操作，从开始第一对到最后一对，这样子最后的元素就是最大元素。
      // 3.针对n个元素重复以上步骤，每次循环排除当前最后一个。
      // 4.重复步骤1~3，直到排序完成。
      function bubbleSort(arr) {
        for(let i = 0; i < arr.length; i++) {
          for(let j = 0; j < arr.length; j++) {
            if(arr[j] > arr[j + 1]) {
              [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
          }
        }
        return arr
      }

      // 计数排序
      // 1.计算出差值d,最小值小于0,加上本身add
      // 2.创建统计数组并统计对应元素个数
      // 3.统计数组做变形，后面的元素等于前面的元素之和,也就是排名数组
      // 4.遍历原始数组,从统计数组中找到正确位置,输出到结果数组
      function conutSort(arr) {
        let max = Math.max(...arr);
        let countArr = new Array(max + 1).fill(0)
       
        for(let i = 0; i < arr.length; i++) {
          countArr[arr[i]] += 1
        }

        let resultArr = [];

        for(let i = 0; i <= max; i++) {
          for(let j = 0; j < countArr[i]; j++) {
            resultArr.push(i)
          }
        }
        return resultArr
      }
      // 快速排序
      // 1.选择数组中间数作为基数，并从数组中取出此基数
      // 2.准备两个数组容器，遍历数组，逐个与基数比对，较小的放左边容器，较大的放右边容器；
      // 3.递归处理两个容器的元素，并将处理后的数据与基数按大小合并成一个数组，返回。  
      function quickSort(arr) {
        if(arr.length <= 1) return arr
        let basicNum = arr.splice(0, 1)
        let left = []
        let right = []
        for(let i = 0; i < arr.length; i++) {
          if(basicNum > arr[i]) {
            left.push(arr[i])
          } else {
            right.push(arr[i])
          }
        }
        console.log(left, right);
        return quickSort(left).concat(basicNum, quickSort(right))
      }
      // 插入排序
      // 1.从第一个元素开始，该元素可以认为已经被排序；
      // 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
      // 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
      // 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
      // 5.重复步骤2~5。
      function insertionSort(arr) {
        for(let i = 0; i < arr.length; i++) {
          let cur = arr[i];
          let j = i - 1;
          while(j >= 0 && cur < arr[j]) {
            arr[j + 1] = arr[j]
            j --
          }
          arr[j + 1] = cur
        }
        return arr
      }
      const data = [1,2,3,4,5,6,7]
      for(let i = 0; i < data.length; i++) {
        if(i === 2) {
          i ++
        }
        console.log(i, 'iiii')
      }
      console.log(insertionSort(arr))
    </script>
</body>
</html>